package com.midea.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
//测试用例
//nfpdmpi
//dvdw
//edvdwfg
public class LeetCode3 {
    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("bbbb"));
        System.out.println(lengthOfLongestSubstring2("bbbb"));
    }
    public static int lengthOfLongestSubstring(String s) {
        //第一种解法，暴力解法（自己写的）
        ArrayList<Character> list = new ArrayList<>();
        int size = 0;
        StringBuffer sb = new StringBuffer(s);
        for (int i = 0;i<s.length();i++){
            if (!list.contains(sb.charAt(i))){
                list.add(sb.charAt(i));
            }else{
                size = Math.max(size,list.size());
                int index = list.indexOf(sb.charAt(i));
                if (index == 0) list.remove(0);
                else list.subList(0,index+1).clear();
                list.add(sb.charAt(i));
            }
        }
        size = Math.max(size,list.size());
        return size;
    }


        //第二种解法，滑动窗口
        /*其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！
        我们只要把队列的左边的元素移出就行了，直到满足题目要求
        一直维持这样的队列，找出队列出现最长的长度时候，求出解！
        时间复杂度：O(n)*/
    public static int lengthOfLongestSubstring2(String s) {
        if (s.length()==0) return 0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int max = 0;
        int left = 0;
        for(int i = 0; i < s.length(); i ++){
            if(map.containsKey(s.charAt(i))){
                left = Math.max(left,map.get(s.charAt(i)) + 1);
            }
            map.put(s.charAt(i),i);
            max = Math.max(max,i-left+1);
        }
        return max;
    }
}
